#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long

using namespace std;

ll dp[10000024];
int main()
{
    ll t, m, w[10024] = {}, v[10024] = {};

    for (ll i = 0; i < 10000024; i++)
        dp[i] = 0;

    cin >> t >> m;

    for (ll i = 1; i <= m; i++)
    {
        cin >> w[i] >> v[i];
    }
    
    for (ll i = 1; i <= m; i++)
    {
        for (ll j = w[i]; j <= t; j++)
        {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[t];

    return 0;
}
